package leetcode_周赛._2022._202205;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/5/29 10:41
 */
public class _29 {
    public static void main(String[] args) {
        System.out.println(new _29().totalSteps(new int[]{5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11}));
    }

    // 6079. 价格减免
    public String discountPrices(String sentence, int discount) {
        String[] arr = sentence.split(" ");
        StringBuilder ans = new StringBuilder();
        double dis = discount * 1.0 / 100;
        for (String s : arr) {
            if (s.startsWith("$") && s.length() > 1) {
                double num = 0;
                boolean flag = false;
                for (int i = 1; i < s.length(); i++) {
                    if (s.charAt(i) >= '0' && s.charAt(i) <= '9') num = num * 10 + (s.charAt(i) - '0');
                    else {
                        flag = true;
                        break;
                    }
                }
                if (flag) ans.append(s);
                else ans.append(String.format("$%.2f", (num - num * dis)));
            } else ans.append(s);
            ans.append(" ");
        }
        ans.deleteCharAt(ans.length() - 1);
        return ans.toString();
    }

    // 6080. 使数组按非递减顺序排列
    // 以当前数为准，往后找到比它小的所有数
    // 找到所有数后，找出这些数字的严格递增，有几个严格递减，就要删几次

    /**
     * 6080. 使数组按非递减顺序排列
     * 算法：单调栈
     * 遍历数组, 往后找出小于当前元素值的连续的数字
     * 找出这些数字的严格递增序列，这些严格递增序列的最大长度就是删除这些数字所需要的操作数
     * 可以使用单调栈来找出最长的递增序列长度
     *
     * @param nums nums
     * @return ans
     */
    public int totalSteps(int[] nums) {
        int n = nums.length;
        Deque<Integer> stack = new ArrayDeque<>();
        int[] cnt = new int[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int tmp = 0;
            while (!stack.isEmpty() && nums[i] >= nums[stack.peek()]) {
                tmp = Math.max(tmp, cnt[stack.peek()]);
                stack.pop();
            }
            if (!stack.isEmpty()) {
                cnt[i] = tmp + 1;
                ans = Math.max(ans, cnt[i]);
            }
            stack.push(i);
        }
        return ans;
    }

}
